#include <stdio.h>
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))

// dp[i] = max(dp[i-1] + a[i], a[i])
int maxSubArray(int* nums, int numsSize){
    int *dp = (int *)malloc(numsSize * sizeof(int));
    dp[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < numsSize; i++) {
        dp[i] = MAX(dp[i - 1] + nums[i], nums[i]);
        max = MAX(max, dp[i]);
    }
    free(dp);

    return max;
}

int main(void)
{
    int a[] = {-2,1,-3,4,-1,2,1,-5,4};
    int len = sizeof(a) / sizeof(a[0]);
    int result = maxSubArray(a, len);
    printf("%d\n", result);
    return 0;
}